#include <stdio.h>
#include <stdlib.h>

#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20

typedef int Vertex;     // 结点数据类型
typedef int WeightType; // 权值数据类型
typedef char DataType;  // 顶点数据类型
// 图的存储结构
// 1.数组(邻接矩阵)表示法
// 若是无向图，则矩阵必定对称，那么只需要存储上三角或者下三角就可以。
// 需要用一个二维数组存储结点之间的关系，还需要用一个一维数组来存储结点信息，另外还有图的顶点数和边数。

// 图结构的定义
typedef struct GNode *PtrToGNode;
struct GNode
{
    int Nv;                                       // 顶点数
    int Ne;                                       // 边数
    WeightType G[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
    DataType Data[MAX_VERTEX_NUM];                // 存储顶点的内容
};
typedef PtrToGNode MGraph;

// 边结构的定义
typedef struct ENode *PtrToENode;
struct ENode
{
    Vertex V1, V2;     // 结点编号
    WeightType weight; // 权重
};
typedef PtrToENode Edge;

// 从零开始创建一个图
MGraph CreateGraph(int VertexNum)
{ // 初始化一个有顶点但是没有边的图
    Vertex V, W;
    MGraph Graph;

    Graph = (MGraph)malloc(sizeof(struct GNode));
    Graph->Nv = VertexNum;
    Graph->Ne = 0;
    // 初始化邻接矩阵
    for (V = 0; V < VertexNum; V++)
    {
        for (W = 0; W < VertexNum; W++)
        {
            Graph->G[V][W] = INFINITY;
        }
    }
    return Graph;
}
void InsertEdge(MGraph Graph, Edge E)
{ // 通过边插入的方式
    Graph->G[E->V1][E->V2] = E->weight;
    // 若是无向图，还需要对称地插入
    Graph->G[E->V2][E->V1] = E->weight;
}
MGraph BuildGraph()
{
    MGraph Graph; // 图
    Edge E;       // 边
    Vertex V;     // 结点
    int Nv, i;    // 结点数，遍历变量

    scanf("%d", &Nv);        // 输入结点数
    Graph = CreateGraph(Nv); // 初始化一个只有结点数没有边信息的图

    scanf("%d", &Graph->Ne); // 输入边数
    if (Graph->Ne != 0)
    {
        E = (Edge)malloc(sizeof(struct ENode)); // 建立边结点
        for (i = 0; i < Graph->Ne; i++)
        {
            scanf("%d %d %d", &E->V1, &E->V2, &E->weight);
            InsertEdge(Graph, E); // 插入边
        }
    }

    for (V = 0; V < Graph->Nv; V++)
    {
        scanf("%c", &(Graph->Data[V]));
    }
    return Graph;
}

// 上面的方法固然有效，但是对于一个稀疏矩阵来说是不是浪费的空间太多了呢？？
// 因此有了下面的一种方法：邻接表(顺序存储与链式存储相结合)
// 将所有邻接与Vi的顶点Vj链成一个单链表，再将所有表头放进一个数组中

// 在Graph2中完成......
